There are many applications in which text or graphic data is digitally encoded, for either storage or transmission purposes. It has long been recognized that regardless of whether or not the data to be transmitted or stored is graphical or textual, economies can be obtained by compressing the data, usually without significant loss of information. One particular example which shall be described in detail in the following portion of this application, is the digital transmission of an image of a newspaper page.
The prior art is replete with source encoding techniques for compressing, see for example, "Optimum Run Length Codes" by Meyr et al in IEEE Transactions on Communications, Volume COM-22, No. 6, June 1974, page 826 et seq; "Two Dimensional Facsimile Source Encoding Based on a Markov Model" by Preuss in NTZ 28 (1975) H. 10, S. 358-363; "Comparison of Redundancy Reducing Codes for Facsimile Transmission of Documents" by Musmann et al, IEEE Transactions on Communications, Volume COM-25, No. 11, November, 1977, page 425 et seq; "Coding of Two-Tone Images" by Huang, IEEE Transactions on Communications, Volume COM-25, No. 11, November, 1977, page 1406 et seq; U.S. Pat. No. 4,163,260; U.S. Pat. No. 4,167,758; U.S. Pat. No. 4,144,547, and "Adaptation of Ordering Techniques for Facsimile Pictures With No Single Element Runs" by Natravali et al appearing in BSTJ, Volume 58, No. 4, April, 1979, pages 857 et seq. Additional suggestions and techniques are found in "Survey of Adaptive Image Coding Techniques by Habibi, IEEE Transactions on Communications, Volume COM-25, No. 11, November, 1977, page 1275 et seq. "Potential Digitalization/Compression Techniques for Shuttle Video" by Habibi et al appearing in IEEE Transactions on Communications, Volume COM-26, No. 11, November 1978, pages 1671 et seq; "A Survey of Digital Picture Coding" by Habibi et al, Computer, May 1974, pages 22 et seq; "Hybrid Coding of Pictorial Data" by Habibi, IEEE Transactions on Communications, May 1974, pages 240 et seq; U.S. Pat. No. 4,173,771; U.S. Pat. No. 4,168,513; U.S. Pat. No. 4,161,757 and U.S. Defensive Publication No. T-985,005.
The digital transmission of an image (whether it be textual or graphic, or a combination) requires that the image be digitized, so that the digital samples of the image can be switched, stored or transmitted. The digitizing process can produce pixels (picture elements) which can be described as a single bit, or a plurality of bits (for example when brightness of the image is to be retained). Regardless of the number of bits required to represent each pixel, image compression is based upon the thesis that most images are correlated i.e., there is some amount of redundancy in the image, and by eliminating the redundancy, the total number of bits required to represent the image can be reduced i.e., compressed.
As is apparent from the prior art cited above, the difficulty with this approach is that, to the extent that mathematical operators are available which are capable of eliminating all or most of the redundancy from a particular bit pattern, they are prohibitively costly to implement because of the extensive computations required. On the other hand, those relatively simple mathematical processes which are simple to implement, and which are capable of eliminating some redundancy in particular bit patterns, are not sufficiently optimized over a population of bit patterns that they can usefully be employed in most real world applications, for example, that of transmitting an image of a newspaper page. To overcome this, the prior art has arranged various types of "adaptive" mechanisms in which the processes employed adapt to the particular bit patterns being subjected to compression. The present invention is an improvement in adaptive compression techniques.
In one particular application, newspaper images, each 22 by 14 inches (or 22".times.14") are scanned at a thousand lines per inch, producing approximately 308.times.10.sup.6 pixels per page. Transmission of that data at approximately 6 Megabits per second enables the transmission of one page per minute. While those parameters are well within the skill of the art, economies can be effected by compressing the data required to describe the image, and a goal originally required was at least a 10:1 compression ratio as an overall average.